package 剑指offer;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @description:
 * @author: ywk
 * @date: 2020-11-01
 */
public class 数组中的最长连续子序列 {
    public static void main(String[] args) {
        System.out.println(MLS(new int[]{5, 0, 1, 2}));
    }

    /**
     * max increasing subsequence
     *
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public static int MLS(int[] arr) {
        // write code here
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < arr.length; i++) {
            map.put(arr[i], 0);
        }
        int max = 1;
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            if (e.getValue() == 0 && map.get(e.getKey() + 1) != null && map.get(e.getKey() + 1) == 0) {
                int start = e.getKey();
                int count = 0;
                while (map.get(start) != null && map.get(start) == 0) {
                    map.put(start++, 1);
                    count++;
                }
                if (count > max) {
                    max = count;
                }
            }

        }
        return max;
    }
}
